package lib

import "sort"

func init() {
	Probs = append(Probs, Problem{
		Num:         18,
		Discription: "四数之和",
		Level:       3,
		Labels: map[string]int{
			"双指针滑动": 1,
			"排序":    1,
			"去重": 1,
		},
	})
}

func FourSum(nums []int, target int) [][]int {    
    n:=len(nums)
    if n<4{
        return [][]int{}
    }

    sort.Ints(nums)
    res:=make([][]int,0)
    for i:=0;i<=n-4;i++{
        for i>0&&i<=n-4&&nums[i]==nums[i-1]{
            i++
        }

        for j:=i+1;j<=n-3;j++{
            for j>i+1&&j<=n-3&&nums[j]==nums[j-1]{
                j++
            }

            left:=j+1
            right:=n-1
            for left<right{
                sum:=nums[i]+nums[j]+nums[left]+nums[right]
                if sum==target{
                    res=append(res, []int{nums[i],nums[j],nums[left],nums[right]})
                    left++
                    for left<right&&nums[left]==nums[left-1]{
                        left++
                    }
                    right--
                    for left<right&&nums[right]==nums[right+1]{
                        right--
                    }
                    continue
                }

                if sum<target{
                    left++
                    for left<right&&nums[left]==nums[left-1]{
                        left++
                    }
                }else{
                    right--
                    for left<right&&nums[right]==nums[right+1]{
                        right--
                    }
                }
            }
        }
    }

    return res
}